package leetcode每日一题.leetcode20213;

/**
 * 1. 问题描述
 *      LIS问题，一道非常经典的算法问题，有多种解法
 *
 * 2. 算法分析
 *      1. 动态规划实现
 *
 * 3. 代码实现
 */
@SuppressWarnings("all")
public class Q004_1_最长递增子序列 {
    /**
     * 动态规划
     * 题解分析：
     *      首先明确什么是最长递增子串，此子串子序列并不是一回事，因为前这是离散的，后者是连续的
     *      所以在问题的分析上有很大的不同
     *      由于最长上升子串一定以数组中的某个元素为结束，所以我们枚举每个结尾，找到以每个元素结束的
     *      最长递增数组，设为dp[i],分析dp[i]的状态如何有前i-1长度的数组来表示呢?
     *      如果当前第i元素大于第j个元素，且j < i,此时一定有dp[i] >= dp[j] + 1,所以以第i个元素结尾
     *      的最长递增长度 dp[i] = max(dp[j]) + 1  其中j < i and nums[j] < nums[i]（因为要求是严格的）
     *      最后枚举出最长的一个即可
     *      动态规划的时间复杂度为O(n^2)  空间复杂度为O(n)
     * @param nums
     * @return
     */
    public int lengthOfLIS1(int[] nums) {
        int n = nums.length;
        int[] dp = new int[n]; // dp[i]的含义：以第i个元素结尾的最长递增子序列
        dp[0] = 1;
        // 考虑dp方程 dp[i] = max(dp[j]) + 1  0 <= j < i
        for(int i = 1; i < n; i++) {
            int max = 0;
            for(int j = 0; j < i; j++) {
                if(max < dp[j] && nums[j] < nums[i]) {
                    max = dp[j];
                }
            }
            dp[i] = max + 1;
        }
        int res = 0;
        for(int x : dp) {
            if(res < x) {
                res = x;
            }
        }
        return res;
    }

    /**
     * 贪心+二分查找
     * 题解分析：
     *      考虑一个简单的贪心，如果我们要使上升子序列尽可能的长，则我们需要让序列上升得尽可能慢，
     *      因此我们希望每次在上升子序列最后加上的那个数尽可能的小。
     * @param nums
     * @return
     */
    public int lengthOfLIS2(int[] nums) {
        return -1;
    }
}
